#include <stdio.h>

#define ARRAYSIZE 32

unsigned long int next = 1;

int rand(void);
void srand(unsigned int seed);
void qsort(int v[], int left, int right);
void printarray(int v[]);

int main()
{
    int i, v[ARRAYSIZE];

    for (i = 0; i < ARRAYSIZE; i++)
    {
        srand(next);
        v[i] = rand();
    }

    printf("before: ");
    printarray(v);

    qsort(v, 0, ARRAYSIZE-1);

    printf("after: ");
    printarray(v);

    return 0;
}

int rand(void)
{
    next = next * 1103512545 + 12345;
    return (unsigned int)(next / 65536) % 32768;
}

void qsort(int v[], int left, int right)
{
    int i, last;
    void swap(int v[], int i, int j);

    if (left >= right)
    {
        return;
    }
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left + 1; i <= right; i++)
    {
        if (v[i] < v[left])
        {
            swap(v, ++last, i);
		}
    }
    swap(v, left, last);
    qsort(v, left, last - 1);
    qsort(v, last+1, right);
}

void swap(int v[], int i, int j)
{
    int temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

void srand(unsigned int seed) { next = seed; }

void printarray(int v[])
{
    for (int i = 0; i < ARRAYSIZE; i++)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
}
